#ifndef __DYNAMICARRAY_H_
#define __DYNAMICARRAY_H_
#include <cstddef>
#include <iostream>
#include <limits.h>

namespace DArray
{
    using ElementType = void *;
    class DynamicArray
    {
        friend bool IsNameEqual(void *ptr1, void *ptr2);
        friend bool IsAgeEqual(void *ptr1, void *ptr2);

    public:
        DynamicArray(size_t capacity = 15);
        DynamicArray(const DynamicArray &a);
        DynamicArray &operator=(const DynamicArray &a);
        ~DynamicArray();

        size_t Size();
        void ReSize(size_t capacity);

        // 尾部插入
        void InsertTail(const ElementType &element);
        // 头部插入
        void InsertHead(const ElementType &element);
        // 中间插入
        void InsertByIndex(int index, const ElementType &element);

        // 按位置删除
        void RemoveByIndex(int index);
        // 按值删除
        void RemoveByElement(const ElementType &element, bool (*equalPtr)(ElementType, ElementType));
        // 按位置查找
        ElementType *FindByIndex(int index);
        ElementType &operator[](int index);
        // 按值查找
        DynamicArray FindByElement(const ElementType &element, bool (*equalPtr)(ElementType, ElementType));
        // 按位置修改
        void UpdataByIndex(int index, const ElementType &element);
        // 按值修改
        void UpdataByElement(const ElementType &oldValue, const ElementType &newValue, bool (*equalPtr)(ElementType, ElementType));
        // 排序
        void Sort(bool (*equalPtr)(ElementType, ElementType));
        // 去重算法
        void Duplicate(bool (*equalPtr)(ElementType, ElementType));
        // 合并两个已经有序的数列
        DynamicArray Merge(const DynamicArray &a, bool (*equalPtr)(ElementType, ElementType));
        // 找交集:
        DynamicArray FndInterSctn(const DynamicArray &a, bool (*equalPtr)(ElementType, ElementType), bool (*equalPtr1)(ElementType, ElementType));
        // 找并集
        DynamicArray FindUnionSet(const DynamicArray &a, bool (*equalPtr)(ElementType, ElementType), bool (*equalPtr1)(ElementType, ElementType));
        // 找补集
        DynamicArray FindDifference(const DynamicArray &a, bool (*equalPtr)(ElementType, ElementType), bool (*equalPtr1)(ElementType, ElementType));

        // 判断两个数列是否相等
        bool operator==(const DynamicArray &a);
        // 二分查找
        size_t BinarySearch(const ElementType &element, bool (*equalPtr)(ElementType, ElementType));
        // 查找一个数列是不是子数列
        bool IsChild(const DynamicArray &a);
        // 查找连续子序列
        bool IsCntnsChilid(const DynamicArray &a);
        // 获取子序列
        DynamicArray subsequence(int index, size_t size);
        // 输出
        void show(void (*PrintPtr)(ElementType));

        // void SetFreePtr();
        // 插入排序
        void InsertSort(size_t start, size_t end, bool (*equalPtr)(ElementType, ElementType));

    private:
        void FastSort(size_t start, size_t end, size_t deepth, size_t MaxDeept, bool (*equalPtr)(ElementType, ElementType));
        // 分组函数
        size_t Partition(size_t start, size_t end, bool (*equalPtr)(ElementType, ElementType));

        ElementType *array;
        size_t capacity;
        size_t size;
        void (*freePtr)(ElementType);               // 数组元素释放的指针
        void (*PrintPtr)(ElementType);              // 打印元素的函数指针
        bool (*SortPtr)(ElementType, ElementType);  // 排序数组
        bool (*equalPtr)(ElementType, ElementType); // 比较指针
        bool (*equalPtr1)(ElementType, ElementType);
    };
}
#endif